﻿#include <iostream>

typedef char TElemType;
typedef struct BiTNode {
    TElemType info;
    struct BiTNode *llink, *rlink;
} BiTNode, *BiTree;


void InitTree(BiTree &BT) {
    BT = NULL;
}


void CreateTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == '#') {
        e = NULL;
    } else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        BT->info = e;
        CreateTree(BT->llink);
        CreateTree(BT->rlink);
    }
}


int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->llink);
    Rh = TreeDepth(BT->rlink);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}

/*
 * 设一棵二叉树的结点结构为（LLINK，INFO，RLINK），root为指向该二叉树根结点的指针，p，q分别指向该二叉树中任意两个结点的指针，
 * 试编写算法ANCENSTOR(ROOT,p,q,r)，找到p和q的最近公共祖先结点。
 *
 * 操作步骤：按非递归后序遍历的方法查找p和q的祖先，当后序遍历访问到p的时候，栈中的结点都是p的祖先，则将栈中元素复制到另一个辅助栈中。
 * 继续遍历到结点q时，将栈中元素从栈顶与辅助栈中去匹配，第一个匹配到的元素就是结点p和q的最近公共祖先
 */

void Ancestor(BiTree root, BiTree p, BiTree q, BiTree r) {
    BiTNode *point = root, *pre = NULL;
    int tree_depth = TreeDepth(root);
    BiTree stack1[tree_depth];
    BiTree stack2[tree_depth];
    int top1 = 0, top2 = 0;  // 初始化两个栈
    r=NULL;  // 默认没有最近公共祖先
    // 查找p的祖先
    while (point || top1 > -1) {
        if (point != NULL && point != p) {
            stack1[top1++] = point;
            point = point->llink;
        } else {
            point = stack1[top1];  //取栈顶元素
            if (point == p) {  // 找到p
                for (int i = 0; i <= top1; i++) {
                    stack2[i] = stack1[1];
                }
                top2 = top1;
            }
            if (stack1[top1] == q) {  // 找到q
                for (int i = top1; i > 0; i--) {  // 将栈中的元素与stack2中匹配
                    for (int j = top2; j > 0; j--) {
                        if (stack1[i] == stack2[j]) {
                            r = stack1[i];  // 最近公共祖先已找到
                        }
                    }
                }
                top1--;  // 退栈
            }
            if (point->rlink && point->rlink != pre) {  // 栈顶元素不是p结点或不是q结点
                point = point->rlink;    // 转向右
                stack1[top1++] = point;
                point = point->llink;
            } else {
                point = stack1[top1--];
                pre = point;  // pre指向刚刚访问过的结点
                point = NULL;  // 访问完毕后，重置p指针，不然该结点又会重新入栈
            }
        }
    }
}

int main() {
    BiTree BT;
    InitTree(BT);

    std::cout << "请按照先序遍历输入输入一棵二叉树（'#'表示空）：";
    CreateTree(BT);
    return 0;
}